package com.company.bs2021;

import java.util.Arrays;

/**
 * <pre>
 * 1．最长和谐子序列（18分)
 * 问题描述:
 * 和谐数组是指一个数组里元素的最大值和最小值之间的差别正好是1。现给定一个整数数组nums，
 * 请在所有可能的子序列中找到最长的和谐子序列的长度并输出最长的和谐子序列。数组的子序列
 * 是一个由数组派生出来的序列，它可以通过删除一些元素或不删除元素、且不改变其余元素的顺
 * 序而得到。
 *
 * 要求:
 * 完成题目对应的程序模板（Harmonious1ySequence）中的方法:
 *  int maxHarmoniouslySequence(int[] nums);
 * 该方法的入口参数nums为给定的整数数组;方法返回值为满足要求的最大和谐子序列的长度。
 *
 * 样例:
 *  样例1
 *   输入: nums = [1,3,2,2,5,2,3,7]
 *   输出:5
 *   解释:最长的和谐子序列是[3,2,2,2,3]，所以输出该和谐子序列的长度为 5
 *
 *  样例2
 *   输入: nums = [1,1,1,1]输出:0
 *   解释:给定的数组中不存在和谐子序列，所以输出结果为0
 *</pre>
 * @author jianf
 * @date 2022年07月06 14:10
 */
public class Harmonious1ySequence {

    /*int maxHarmoniouslySequence(int[] nums){
        int lenth0 = 0,lenth1=0;
        int maxLen = 0;
        for (int i=0;i< nums.length; i++){
            lenth0 = 0;
            lenth1=0;
            int start = nums[i];
            boolean eq = true;
            System.out.printf("起始%d: [%d,", start,start);
            for (int j = i+1; j < nums.length; j++) {
                if(start - nums[j] <=1 && start - nums[j] >= 0){
                    if (start !=nums[j]) {
                        eq = false;
                    }
                    lenth0 ++;
                    System.out.printf("%d, ", nums[j]);
                }
                if(start - nums[j] >= -1 && start - nums[j] <= 0){
                    if (start !=nums[j]) {
                        eq = false;
                    }
                    lenth1 ++;
                    System.out.printf("%d, ", nums[j]);
                }
            }

            System.out.printf("] 长度为：%d\n",Math.max( lenth0,lenth1) +1);
            if (lenth0+1 > maxLen && eq == false || lenth1 + 1 > maxLen ){
                maxLen = Math.max( lenth0,lenth1) +1;
            }
        }
        return maxLen;
    }*/

    int maxHarmoniouslySequence(int[] nums){
        Arrays.sort(nums);
        int begin = 0,res =0;
        for (int end = 0; end < nums.length ; end++) {
            //当差值大于1时，说明当前的元素不能做为起始位置
            while (nums[end] - nums[begin] > 1){
                begin++;
            }
            if(nums[end] - nums[begin] ==1){
                res = Math.max(res, end - begin +1);
            }
        }
        return res;
    }
    public static void main(String[] args) {
//        int[] nums = {1,3,2,2,5,2,3,7};
        int[] nums = {9,3,5,2,3,5,6,6,7,9,7};
//        int[] nums = {1,1,1,1,1};
        Harmonious1ySequence hs = new Harmonious1ySequence();
        int r = hs.maxHarmoniouslySequence(nums);
        System.out.println(r);
    }
}
